package no26;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/20 23:58
 * II 重排链表
 * https://leetcode.cn/problems/LGjMqU/
 */
public class Solution01 {

    // 方法一 O(n) 时间复杂度 O(1) 空间复杂度
    public void reorderList(ListNode head) {
        // 结果为左半链表和右半链表逆序的交替合并
        // 先找到链表的中间节点
        ListNode midListNode = findMidListNode(head);
        // 看成左右两个链表, 并将右侧链表进行反转
        ListNode l1 = head;
        ListNode l2 = midListNode.next;
        midListNode.next = null; // 断开原来的链表
        l2 = reverseList(l2); // 反转 l2 链表
        mergeList(l1, l2); // 合并链表
    }

    // 找到链表的中间节点或者中间靠前的节点
    public ListNode findMidListNode(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }


    // 反转链表并返回反转链表的头指针
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = curNext;
        }
        return pre;
    }

    // 交替合并链表 l1 和链表 l2
    public void mergeList(ListNode l1, ListNode l2) {
        ListNode curL1 = l1;
        ListNode curL2 = l2;
        while (curL1 != null && curL2 != null) {
            ListNode cur1Next = curL1.next;
            ListNode cur2Next = curL2.next;
            curL1.next = curL2;
            curL1 = cur1Next;
            curL2.next = curL1;
            curL2 = cur2Next;
        }
    }

    // 方法二 顺序表存储 O(n) 时间与空间复杂度
    public void reorderList2(ListNode head) {
        // 将链表存入顺序表
        List<ListNode> list = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            list.add(cur);
            cur = cur.next;
        }
        // 双指针进行重排
        int start = 0;
        int end = list.size()-1;
        while (start < end) {
            list.get(start).next = list.get(end);
            start++;
            if (start == end) {
                break;
            }
            list.get(end).next = list.get(start);
            end--;
        }
        list.get(start).next = null;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
